package demo;

public class MyLinkedList<E> {
    private Node<E> first;
    private Node<E> last;
    private int size;

    private static class Node<E>{
        E item;
        Node<E> next;
        Node<E> prev;
        private Node(E e){
            item = e;
        }
    }
    public boolean add(E e){
        Node<E> node = new Node<>(e);
        if (size == 0){ //添加第一个Node节点
            first = node;
            last = node;
        }else {         //添加第二个以后的Node节点
            node.prev = last;
            last.next = node;
            last = node;
        }
        size++;
        return true;
    }
    private Node<E> find(int index){
        Node<E> node;
        if (index < size>>1) {
            System.out.println("正向查找 ");
            node = first;
            for (int i = 0; i<index; i++) {
                node = node.next;
            }
        }else {
            System.out.println("反向查找 ");
            node = last;
            for (int i=size-1; i>index; i--){
                node = node.prev;
            }
        }
        return node;
    }

    public void add(int index, E e){
        if(index<0 || index>size){
            throw new IndexOutOfBoundsException("越界："+index);
        }
        if(size == index){ //处理末尾节点和没有元素的情况
            add(e);
            return;
        }
        Node<E> newNode = new Node<>(e);
        if(index == 0){
            System.out.println("插头：单独插入头节点");
            first.prev = newNode;
            newNode.next = first;
            first = newNode;
            size++;
            return;
        }
        //查找插入位置node
        Node<E> node = find(index);
        Node<E> prev = node.prev;
        //建立链接关系
        prev.next = newNode;
        newNode.next = node;
        node.prev = newNode;
        newNode.prev = prev;
        size++;
    }

    /**
     * 获取指定位置上的数据
     * @param index 位置
     * @return 存储在链表上的数据
     */
    public E get(int index){
        if (index<0 || index>=size){
            throw new IndexOutOfBoundsException("越界："+index);
        }
        Node<E> node = find(index);
        return node.item;
    }

    @Override
    public String toString() {
        //如果集合长度为0 返回  ”[]“
        if (size == 0) return "[]";
        //[Tom, Jerry, Lee, Wang, John, Andy]
        StringBuilder buf = new StringBuilder("[");
        //第一个元素单独处理，这样可以解决逗号比元素少一个的问题
        buf.append(first.item);
        Node<E> node = first.next;
        for(int i=1; i<size; i++){
            buf.append(", ").append(node.item);
            node = node.next;
        }
        return buf.append("]").toString();
    }
}




